Khuếch đại biên độ là một kĩ thuật cho phép khuếch đại trên một vùng không gian con xác định của một trạng thái lượng tử. Những ứng dụng của khuếch đại biên độ thường dẫn đến sự tăng tốc bậc hai trên những thuật toán cổ điển tương ứng. Nó có thể được coi như là một sự tổng quát hóa của thuật toán Grover.

Thuật toán của Grover

Thuật toán của Grover tìm kiếm trên một bộ dữ liệu không có cấu trúc hoặc một danh sách không có thứ tự với N phần tử trong đó một phần tử được đánh dấu, chỉ sử dụng O ( N ) {\displaystyle O({\sqrt {N}})} truy vấn thay vì Ω(N) truy vấn dựa theo cách cổ điển. Theo cách cổ điển, Ω(N) truy vấn được yêu cầu chỉ khi chúng ta cho phép những thuật toán xác suất chặn lỗi.

Đếm lượng tử

Đếm lượng tử giải quyết một cách tổng quát các vấn đề tìm kiếm. Phương pháp này giải quyết vấn đề thông qua đếm số lượng các phần tử được đánh dấu trong một danh sách không có thứ tự, thay vì chỉ phát hiện ra khi một phần tử tồn tại. Đặc biệt hơn nữa, nó có thể đếm số lượng những phần tử được đánh dấu trong danh sách N phần tử, với lỗi  thuộc trong khoảng  Θ ( ( 1 / ε ) ∗ s q r t ( N / k ) ) {\displaystyle \Theta ((1/\varepsilon )*sqrt(N/k))} truy vấn, trong đó  k {\displaystyle k} là số lượng phần tử được đánh dấu trong danh sách. Chính xác hơn nữa, thuật toán có đầu ra k ′ {\displaystyle k'} là một ước lượng với k {\displaystyle k} , số lượng phần tử được đánh dấu, cùng với độ chính xác phép đo | k − k ′ | ⩽ ε k {\displaystyle |k-k'|\leqslant \varepsilon k} .